package com.aurora.leetcode.answer;

import com.alibaba.fastjson.JSON;

import java.sql.Array;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author : Aurora
 * @date : 2024/5/17 08:43
 * @description
 * <p>15. 三数之和</p>
 * <p>给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k </p>
 * <p>，同时还满足 nums[i] + nums[j] + nums[k] == 0 。</p>
 * <p>请你返回所有和为 0 且不重复的三元组。</p>
 * <p>注意：答案中不可以包含重复的三元组。</p>
 * <p>example1</p>
 * <p>输入：nums = [-1,0,1,2,-1,-4]</p>
 * <p>输出：[[-1,-1,2],[-1,0,1]]</p>
 * <p>解释：
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。</p>
 *
 * <p>example2</p>
 * <p>输入：nums = [0,1,1]</p>
 * <p>输出：[]</p>
 * <p>解释：唯一可能的三元组和不为 0 。</p>
 *
 * <p>example3</p>
 * <p>输入：nums = [0,0,0]</p>
 * <p>输出：[[0,0,0]]</p>
 * <p>解释：唯一可能的三元组和为 0 。</p>
 */
public class ThreeSum_15 {
    //方法一：map+字符串去重
    public List<List<Integer>> threeSum(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; ++i){
            map.put(nums[i], i);
        }
        List<List<Integer>> result = new ArrayList<>();
        Map<String, Integer> onlyOne = new HashMap<>();
        for(int i=0; i<nums.length; ++i){
            for(int j=i+1; j<nums.length; ++j){
                int temp = nums[i]+nums[j];
                Integer integer = map.get(temp * -1);
                if(integer != null && integer != i && integer != j){
                    String judge = nums[i]+""+nums[j];
                    if(onlyOne.get(judge) == null){
                        makeOnlyOne(nums[i], nums[j], temp*-1, onlyOne);
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(temp*-1);
                        result.add(list);
                    }
                }
            }
        }
        return result;
    }
    public void makeOnlyOne(int one, int two, int three, Map<String, Integer> map){
        map.put(one+""+two, 1);
        map.put(two+""+one, 1);
        map.put(one+""+three, 1);
        map.put(three+""+one, 1);
        map.put(two+""+three, 1);
        map.put(three+""+two, 1);

    }

    //方法二：排序+双指针
    public List<List<Integer>> threeSum2(int[] nums){
        //排序
       Arrays.sort(nums);
       //双指针遍历
       List<List<Integer>> result = new ArrayList<>();
       for(int i=0; i<nums.length; ++i){
           int left = i+1, right=nums.length-1;
           if(i>0 && nums[i] == nums[i-1])
               continue;
           while(left < right){
               int num = nums[i] + nums[left] + nums[right];
               if(num < 0){
                   left ++ ;
               }else if (num > 0){
                   right --;
               }else{
                   List<Integer> temp = new ArrayList<>();
                   temp.add(nums[i]);
                   temp.add(nums[left]);
                   temp.add(nums[right]);
                   result.add(temp);
                   while(left<right && nums[left] == nums[left+1])left++;
                   while(left<right && nums[right] == nums[right-1])right--;
                   left++;
                   right--;
               }
           }
       }
       return result;
    }
    public static void main(String[] args) {
        ThreeSum_15 obj = new ThreeSum_15();
//        int[] arr = new int[]{-1,0,1,2,-1,-4};
        int[] arr = new int[]{-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
//        System.out.println(JSON.toJSONString(obj.threeSum(arr)));
        System.out.println(JSON.toJSONString(obj.threeSum2(arr)));


    }
}
